package com.example.sprintbootarithmetic.sort.Quicksort;


import com.example.sprintbootarithmetic.sort.BubbleSorting.BubbleSortings;
import com.example.sprintbootarithmetic.sort.InsertSort.InsertSort;
import com.example.sprintbootarithmetic.sort.ShellSort.ShellSort;
import com.example.sprintbootarithmetic.sort.Util.TimeTest;

/**
 * ��������
 *
 * @param
 * @description:��������
 * @return: null
 * @author: daixingyu
 * @date: 2021-07-11  22:11
 */
public class QuickSort {
    public static void quickSort(int[] sum, int left, int right) {
        int pivot = sum[(left + right) / 2];
        int t = 0;
        int l = left;
        int r = right;
        while (l < r) {
            while (pivot > sum[l]) {
                l++;
            }
            while (pivot < sum[r]) {
                r--;
            }
            //�˳�����
            if (l >= r) {
                break;
            }
            //����
            t = sum[l];
            sum[l] = sum[r];
            sum[r] = t;
            //������󣬷������arr[l]==prvot,r--����ǰ�ƶ�
            if (sum[l] == pivot) {
                r--;
            }
            //������󣬷������arr[r]==prvotֵ ���l++ �����ƶ�
            if (sum[r] == pivot) {
                l++;
            }
        }
        //�ж��Ƿ���ȣ���Ҫ��l����++�Ͷ�r����--,���������������
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            quickSort(sum, left, r);
        }
        if (right > l) {
            quickSort(sum, l, right);
        }
    }

    /*public static void quickSort2(int arr[], int left, int right) {
        int l = left;
        int r = right;
        int pirvot = arr[(left + right) / 2];
        int t = 0;
        while (l < r) {
            while (pirvot > arr[l]) {
                l++;
            }
            while (pirvot < arr[r]) {
                r--;
            }
            if (l > r) {
                break;
            }
            t = arr[l];
            arr[l] = arr[r];
            arr[r] = t;
            if (arr[l] == pirvot) {
                r--;
            }
            if (arr[r] == pirvot) {
                l++;
            }
        }
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            quickSort2(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }
    }*/

    public static void main(String[] args) {
        TimeTest TimeTest = new TimeTest();
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i] = (int) (Math.random() * 80000);
        }
        System.out.println("");
        System.out.println("ð����������ʱ��֮ǰ��");
        String starttime = TimeTest.starttime();
        System.out.println(starttime);
        BubbleSortings.sortCustomer(array);
        System.out.println("����ʱ��֮��" + TimeTest.starttime());
        /**
         *��������
         * @description:
         * @param args
         * @return: void
         * @author: daixingyu
         * @date: 2021-07-01  15:06
         */
        int[] array2 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array2[i] = (int) (Math.random() * 80000);
        }
        System.out.println("");
        System.out.println("ϣ����������ʱ��֮ǰ��");
        String starttime2 = TimeTest.starttime();
        System.out.println(starttime2);
        ShellSort.shellsort(array2);
        System.out.println("����ʱ��֮��" + TimeTest.starttime());
        /**
         *��������
         * @description:
         * @param args
         * @return: void
         * @author: daixingyu
         * @date: 2021-07-01  15:06
         */
        int[] array3 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array3[i] = (int) (Math.random() * 80000);
        }
        System.out.println("");
        System.out.println("������������ʱ��֮ǰ��");
        String starttime3 = TimeTest.starttime();
        System.out.println(starttime3);
        InsertSort.InsertSort(array3);
        System.out.println("����ʱ��֮��" + TimeTest.starttime());
        /**
         *��������
         * @description:
         * @param args
         * @return: void
         * @author: daixingyu
         * @date: 2021-07-01  15:06
         */
        int[] array4 = new int[80000000];
        for (int i = 0; i < 80000000; i++) {
            array4[i] = (int) (Math.random() * 80000000);
        }
        System.out.println("");
        System.out.println("������������ʱ��֮ǰ��");
        String starttime4 = TimeTest.starttime();
        System.out.println(starttime4);
        quickSort(array4, 0, array4.length - 1);
        System.out.println("����ʱ��֮��" + TimeTest.starttime());
    }
}
